package developer.算法.链表.回文链表;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Stack;

/**
 * @author zhangyongkang
 * @time 2024/6/27 20:22
 * @description 给你一个单链表的头节点 head ，请你判断该链表是否为
 * 回文链表
 * 。如果是，返回 true ；否则，返回 false 。
 */

public class Solution_self {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1, new ListNode(3)))));
//        boolean palindrome = MinCha.isPalindrome(head);
//        System.out.println(palindrome);

        Solution3 solution3 = new Solution3();
        System.out.println(solution3.isPalindrome(head));
    }

    static class Solution3 {
        //快慢指针 如果快指针走到终点  那么说明慢指针走到了中点
        public boolean isPalindrome(ListNode head) {
            Stack<Integer> stack = new Stack<>();
            ListNode fastNode = head;
            ListNode slowNode = head;

            //这个循环结束了 说明
            while (fastNode != null && fastNode.next != null) {
                stack.push(slowNode.val);
                fastNode = fastNode.next.next;
                slowNode = slowNode.next;
            }

            while (slowNode != null) {
                if (stack.isEmpty()) {
                    return false;
                }
                Integer pop = stack.pop();
                if (!pop.equals(slowNode.val)) {
                    return false;
                }
                slowNode = slowNode.next;

            }
            return true;
        }
    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static class Solution {


        public static boolean isPalindrome(ListNode head) {
            List<ListNode> nodeList = new ArrayList<>();
            while (head.next != null) {
                nodeList.add(head);
                head = head.next;
            }
            nodeList.add(head);
            int a = 0;
            int b = nodeList.size() - 1;
            while (a <= b) {
                ListNode nodea = nodeList.get(a);
                ListNode nodeb = nodeList.get(b);
                if (!Objects.equals(nodeb.val, nodea.val)) {
                    return false;
                }
                a++;
                b--;
            }
            return true;
        }

    }
}
